Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Microsoft Medium Problems
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Largest Palindromic Number

Problem Statement

Given a string s containing 0 to 9 digits, create the largest possible palindromic number using the string characters. It should not contain leading zeroes.

A palindromic number reads the same backward as forward.

If it's not possible to form such a number using all digits of the given string, you can skip some of them.

Examples

Example 1

  • Input: s = "323211444"
  • Expected Output: "432141234"
  • Justification: This is the largest palindromic number that can be formed from the given digits.

Example 2

  • Input: s = "998877"
  • Expected Output: "987789"
  • Justification: "987789" is the largest palindrome that can be formed.

Example 3

  • Input: s = "54321"
  • Expected Output: "5"
  • Justification: Only "5" can form a valid palindromic number as other digits cannot be paired.

Constraints:

  • 1 <= num.length <= 105
  • num consists of digits.

Solution

To solve this problem, the goal is to create the largest palindromic number possible using the digits from the given input number. A palindrome reads the same backward as forward, so our approach is to build the number symmetrically.

First, we count the frequency of each digit in the input number using an array of size 10 (for digits 0-9). Then, we construct the first half of the palindrome by appending each digit as many times as half of its frequency, starting from the highest digit (9) down to the lowest (0). If there is a digit with an odd frequency, we select the largest such digit to be the center of the palindrome. Finally, we append the reversed first half to the original first half (with the center digit, if any) to complete the palindrome. This ensures that the number is the largest possible palindrome.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create a StringBuilder named firstHalf to store the first half of the palindrome.
    • Create an integer array frequency of size 10 to count the frequency of each digit (0-9).
    • Initialize a variable middle to -1 to store the center digit if needed.
  2. Count Frequencies:

    • Iterate through each character in the input string num.
    • For each character, convert it to an integer and increment its corresponding frequency in the frequency array.
  3. Build the First Half of the Palindrome:

    • Iterate from the highest digit (9) to the lowest digit (0).
    • For each digit, if its frequency is greater than 1:
      • Use while loop to add pairs of the digit to firstHalf until less than 2 of that digit remains.
      • If there is one of the digit left and middle is still -1, set middle to this digit (largest odd-count digit).
  4. Build the Full Palindrome:

    • Create secondHalf as a reversed copy of firstHalf.
    • If middle is not -1, append middle to firstHalf.
    • Append the reversed secondHalf to firstHalf.
  5. Return the Result:

    • If firstHalf has any digits, return firstHalf as the final palindrome.
    • Otherwise, return "0".

Algorithm Walkthrough

Image
  1. Initialize Data Structures:

    • firstHalf = ""
    • frequency = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    • center = -1
  2. Count Frequencies:

    • Process each digit in num:
      • 3: frequency[3] becomes 1.
      • 2: frequency[2] becomes 1.
      • 3: frequency[3] becomes 2.
      • 2: frequency[2] becomes 2.
      • 1: frequency[1] becomes 1.
      • 1: frequency[1] becomes 2.
      • 4: frequency[4] becomes 1.
      • 4: frequency[4] becomes 2.
      • 4: frequency[4] becomes 3.
    • Final frequency = [0, 2, 2, 2, 3, 0, 0, 0, 0, 0]
  3. Build the First Half of the Palindrome:

    • Iterate from digit 9 to 0:
      • 9: frequency[9] is 0, skip.
      • 8: frequency[8] is 0, skip.
      • 7: frequency[7] is 0, skip.
      • 6: frequency[6] is 0, skip.
      • 5: frequency[5] is 0, skip.
      • 4: frequency[4] is 3:
        • Append "4" to firstHalf, firstHalf = "4", count becomes 1.
        • center is set to 4 since it's the largest digit with an odd frequency.
      • 3: frequency[3] is 2:
        • Append "3" to firstHalf, firstHalf = "43", count becomes 0.
      • 2: frequency[2] is 2:
        • Append "2" to firstHalf, firstHalf = "432", count becomes 0.
      • 1: frequency[1] is 2:
        • Append "1" to firstHalf, firstHalf = "4321", count becomes 0.
      • 0: frequency[0] is 0, skip.
    • Final firstHalf = "4321"
  4. Build the Full Palindrome:

    • Create secondHalf as a reversed copy of firstHalf, secondHalf = "1234".
    • center is 4, so add 4 to firstHalf, making it 43214.
    • Append secondHalf to firstHalf, firstHalf = "432144321".
  5. Return the Result:

    • firstHalf has digits, so return firstHalf.toString(), which is "432144321".

So, the largest palindromic number that can be formed from "323211444" is "432144321".

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: , where n is the length of the input string. The algorithm involves iterating over the input string once for frequency counting and then iterating over the frequency array (constant size of 10).

  • Space Complexity: Space Complexity: , where (n) is the length of the input string.

    • Frequency Array: space.
    • First Half StringBuilder: Up to space in the worst case.
    • Middle String: space.
Largest Palindromic Number (medium)
Remove Duplicate Letters (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis